package com.lazily.map_;


import java.util.HashMap;

/**
 * @Author:  GZQ
 * @date:  2025/6/3 16:26
 * @description: HashsMap 源码分析 + 解读
 * @version: 1.0
 */

@SuppressWarnings({"all"})
public class HashMapSource1 {
	// 程序入口
	public static void main(String[] args) {
		HashMap map = new HashMap();
		map.put("java", 10);//ok
		map.put("php", 10);//ok
		map.put("java", 20);//替换 value

		System.out.println("map=" + map);//

		// 源码分析 + 解读
		/*
			1.  执行构造器 new HashMap()
				初始化加载因子 loadfactor = 0.75
				HashMap$Node[] table = null
			2. 	执行put 调用 hash方法, 计算 key的 hash值 (h = key.hashCode()) ^ (h >>> 16);
				public V put(K key, V value) { // K = "java" value = 10
					return putVal(hash(key), key, value, false, true);
				}
			3. 执行 putVal
			final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
						   boolean evict) {
				Node<K,V>[] tab; Node<K,V> p; int n, i; //辅助变量
				// 如果底层的table 数组为 null, 或者 length = 0, 就扩容到16
				if ((tab = table) == null || (n = tab.length) == 0)
					n = (tab = resize()).length;
				// 取出hash值对应的table的索引位置的Node, 如果为null, 就直接把加入的k-v,
				// 创建成一个 Node, 加入该位置即可
				if ((p = tab[i = (n - 1) & hash]) == null)
					tab[i] = newNode(hash, key, value, null);
				else {
					Node<K,V> e; K k; // 辅助变量
					// 如果table的索引位置的key的hash相同和新的key的hash值相同,
					// 并满足(table现有的结点的key和准备添加的key是同一个对象 || equals返回真)
					// 就认为不难加入新的k-v
					if (p.hash == hash &&
						((k = p.key) == key || (key != null && key.equals(k))))
						e = p;
					else if (p instanceof TreeNode) // 如果当前的table的已有的Node 是红黑树, 就按照红黑树的方式处理
						e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
					else {
						// 如果找到的结点, 后面是链表, 就循环比较
						for (int binCount = 0; ; ++binCount) { // 死循环
							if ((e = p.next) == null) { // 如果整个链表，没有和他相同, 就加到该链表的最后
								p.next = newNode(hash, key, value, null);
								// 加入后, 判断当前列表的个数, 是否已经到8个，到8个，后
								// 就调用 treeifyBin 方法进行红黑树的转换
								if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
									treeifyBin(tab, hash);
								break;
							}
							if (e.hash == hash && // 如果在循环比较过程中, 发现有相同, 就break, 就只是替换value
								((k = e.key) == key || (key != null && key.equals(k))))
								break;
							p = e;
						}
					}
					if (e != null) { // existing mapping for key
						V oldValue = e.value;
						if (!onlyIfAbsent || oldValue == null)
							e.value = value; // 替换, key对应value
						afterNodeAccess(e);
						return oldValue;
					}
				}
				++modCount; // 每增加一个Node, 就size++
				if (++size > threshold) // 如size > 临界值, 就扩容
					resize();
				afterNodeInsertion(evict);
				return null;
			}

			4. 关于树化(转成红黑树)
			// 如果table 为null, 或者大小没有到 64, 就暂时不树化, 而是进行扩容
			// 否则才会真正的树化 -> 剪枝
			 final void treeifyBin(Node<K,V>[] tab, int hash) {
				int n, index; Node<K,V> e;
				if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
					resize();

			｝

		 */


	}

	// 扩容机制 [和HashSet相同]
	/**
	 * 1. HashMap底层维护了Node类型的数组table，默认为null
	 * 2. 当创建对象时，将加载因子(loadfactor)初始化为0.75.
	 * 3. 当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，
	 *    如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key
	 *    是否相等，如果相等，则直接替换val；如果不相等需要判断是树结构还是链表结构,
	 * 	  做出相应处理。如果添加时发现容量不够，则需要扩容。
	 * 4. 第1次添加，则需要扩容table容量为16，临界值(threshold)为 12 (16*0.75)
	 * 5. 以后再扩容，则需要扩容table容量为原来的2倍(32), 临界值为原来的2倍, 即24,依次类推
	 * 6. 在JaVa8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8),
	 * 	  并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)
	 */
}
